Fixed point

Time: O(LogN); Space: O(1); easy

Given an array A of distinct integers sorted in ascending order, return the smallest index i that satisfies A[i] == i. Return -1 if no such i exists.

Example 1:

Input: A = [-10,-5,0,3,7]

Output: 3

Explanation:

  • For the given array, A[0] = -10, A[1] = -5, A[2] = 0, A[3] = 3,

  • thus the output is 3.

Example 2:

Input: A = [0,2,5,8,17]

Output: 0

Explanation:

  • A[0] = 0, thus the output is 0.

Example 3:

Input: A = [-10,-5,3,4,7,9]

Output: -1

Explanation:

  • There is no such i that A[i] = i, thus the output is -1.

Constraints:

  • 1 <= len(A) < 10^4

  • -10^9 <= A[i] <= 10^9

1. Binary Search [O(LogN), O(1)]

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def fixedPoint(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        left, right = 0, len(A)-1

        while left <= right:
            mid = left + (right-left) // 2
            if A[mid] >= mid:
                right = mid - 1
            else:
                left = mid + 1

        return left if A[left] == left else -1

[2]:

s = Solution1()

A = [-10,-5,0,3,7]
assert s.fixedPoint(A) == 3

A = [0,2,5,8,17]
assert s.fixedPoint(A) == 0

A = [-10,-5,3,4,7,9]
assert s.fixedPoint(A) == -1